Định lý nhỏ Fermat phát biểu rằng nếu p là số nguyên tố và 1 ≤ a < p {\displaystyle 1\leq a<p} , thì

a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} .

Nếu ta muốn kiểm tra số n có là nguyên tố không, ta lấy ngẫu nhiên các số a' và kiểm tra xem đẳng thức trên có đúng không. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đẳng thức đúng với nhiều giá trị của a, ta có thể nói rằng n là số nguyên tố với xác suất nào đó, hay là một số giả nguyên tố (pseudoprime).

Có thể phép thử sẽ cho ta một kết quả sai.

Số a mà

a n − 1 ≡ 1 ( mod n ) {\displaystyle a^{n-1}\equiv 1{\pmod {n}}}

trong khi n là hợp số được gọi là một giả Fermat.

Còn nếu có số a mà

a n − 1 ≢ 1 ( mod n ) {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}

thì a được xem như một bằng chứng Fermat chứng tỏ n là hợp số.